Cloud computing systems, in which the clients rent and share computing resources of third party platforms such as Amazon Elastic Cloud, Microsoft Azure, etc., have gained widespread use in recent years. Provisioned with a large pool of hardware and software resources, these cloud computing systems enable clients to perform computations on a vast amount of data without setting up their own infrastructure [Ambrust]. However, providing the cloud service provider with the client data in plaintext form to carry out the computations results in complete loss of data privacy.
Homomorphic encryption [Rivest] is an approach to tackle the problem of preserving data privacy, which can allow the cloud service providers to perform specific computations directly on the encrypted client data, without requiring private decryption keys. Recently, fully homomorphic encryption (FHE) schemes [e.g., Gentry] have been proposed, which enable performing any arbitrary computation on encrypted data. However, FHE schemes are currently impractical for mobile cloud computing applications due to extremely large cipher text size. For instance, to achieve 128-bit security, the client is required to exchange a few Giga bytes of ciphertext with the cloud server, for each bit of the plain text message. [Gentry].
Yao's garbled circuits approach [Yao 1982; Yao 1986] is a potential alternative to FHE schemes that can drastically reduce the ciphertext size. Any computation can be represented using a Boolean circuit, for which, there exists a corresponding garbled circuit. Each gate in a garbled circuit can be unlocked using a pair of input wire keys that correspond to the underlying plaintext bits; and the association between the wire keys and the plaintext bits is kept secret from the cloud server that performs the computation. Unlocking a gate using a pair of input wire keys reveals an output wire key, which, in turn, serves as an input wire key for unlocking the subsequent gate in the next level of the circuit. Thus, garbled circuits can enable oblivious evaluation of any arbitrary function, expressible as a Boolean circuit, on a third-party cloud server.
While garbled circuits preserve the privacy of client data, they are, however, one time programs— using the same version of the circuit more than once compromises the garbled circuit and reveals to an adversarial evaluator whether the semantics have changed or remained the same for a set of input and output wires between successive evaluations. Expecting the client to create a new version of the garbled circuit for each evaluation, however, is an unreasonable solution, since creating a garbled circuit is at least as expensive as evaluating the underlying Boolean circuit! Thus, in contrast to FHE schemes such as that of Gentry, that can directly delegate the desired computation to the cloud servers, a scheme using garbled circuits, presents the additional challenge of efficiently delegating to the cloud servers the creation of garbled circuit.
In works related to the field of the present invention, homomorphic encryption is an approach that enables performing computations directly on the encrypted data, without requiring private decryption keys. For example, in the RSA public key system, the product of two ciphertext messages produces a ciphertext corresponding to the product of the underlying plain text messages [Rivest]. Domingo-Ferrer present a homomorphic scheme that represents ciphertext as polynomials, allowing both addition and multiplication operations on the underlying plain text; however, in this scheme, multiplication operations drastically increase the size of the cipher text. Recently, fully homomorphic encryption (FHE) schemes [e.g., Gentry] have been proposed, which enable performing any arbitrary computation on encrypted data. However, FHE schemes are currently impractical for cloud computing applications due to extremely large cipher text size.
Yao's garbled circuits have been primarily used in conjunction with oblivious transfer protocols for secure two-party computation. [Yao 1982; Yao 1986 Lindell 2009 II]. Lindell 2009 I presents an excellent survey of secure multiparty computation, along with numerous potential applications, such as privacy preserving data mining, private set intersection, electronic voting and electronic auction. A number of secure two-party and multiparty computation systems have been built over the years. [e.g., Henecka; Malkhi; Ben-David]. Note that in secure multiparty computation systems multiple parties hold private inputs and receive the result of the computation; however, in a secure cloud computing system, such as in the present invention, while multiple parties participate in the creation of garbled circuits, only the client holds private inputs and obtains the result of the computation in garbled form. (As discussed below, in the present invention, secure multiparty computation protocols [Goldreich 2004; Goldreich 1987; Beaver; Rogaway] have been adapted, for building a secure and verifiable cloud computing for mobile systems.)
Twin clouds [Bugiel] is a secure cloud computing architecture, in which the client uses a private cloud for creating garbled circuits and a public commodity cloud for evaluating them. While a new garbled circuit is constructed for each evaluation, note that the cost of constructing a garbled circuit is at least as expensive as the cost of evaluating the underlying Boolean circuit. Moreover, while Twin clouds uses a private cloud for creating the garbled circuits, the present solution, on the other hand, employs multiple public cloud servers for creating as well as evaluating the garbled circuits.
While FHE schemes currently remain impractical, they, however, offer interesting constructions, such as reusable garbled circuits [Goldwasser] and verifiable computing capabilities that permit a client to verify whether an untrusted server has actually performed the requested computation [Gennaro]. In the system of the present invention, the client is enabled to efficiently verify whether an untrusted server has actually evaluated the garbled circuit, without relying on any FHE scheme.
Carter proposed an atypical secure two party computation system with three participants: Alice, Bob and a Proxy. In their work, Bob is a webserver that creates garbled circuits, and Alice is a mobile device that delegates the task of evaluating the garbled circuits to the Proxy, which is a cloud server. It is noted that the computation and adversary models in Carter are very different from that of the present invention. First, in Carter's work, being a secure two party computation system, both Alice and Bob provide private inputs for the computation that they wish to perform jointly; however, in the present secure cloud computing model, only one party, i.e., the mobile client, provides inputs and obtains result of the computation in garbled form. Second, Carter's scheme requires that neither Alice nor Bob can collude with the Proxy; in a sharp contrast, the present method preserves the privacy of the client data even if the evaluating server colludes with all but one of the cloud servers that participated in the creation of the garbled circuit.